package leetcode101.mathematical_problem;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code11
 * @Description 67. 二进制求和
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 *
 * 输入为 非空 字符串且只包含数字 1 和 0。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-26 11:39
 */
public class Code11 {

    public static void main(String[] args) {
        System.out.println(addBinary("1010", "1011"));
    }

    public static String addBinary(String a, String b) {
        int n = a.length(), m = b.length(), num1, num2, sum, tag = 0;
        StringBuilder sb = new StringBuilder(Math.max(n, m) + 1);
        int aIndex = n - 1;
        int bIndex = m - 1;

        while (aIndex > -1 && bIndex > -1) {
            num1 = a.charAt(aIndex--) - '0';
            num2 = b.charAt(bIndex--) - '0';
            sum = num1 + num2 + tag;
            if (sum > 1) {
                sb.insert(0, sum % 2);
                tag = 1;
            } else {
                sb.insert(0, sum);
                tag = 0;
            }
        }

        if (aIndex == -1 && bIndex == -1) {
            sb.insert(0, tag == 1 ? tag : "");
            return new String(sb);
        }

        while (aIndex > -1) {
            sum = a.charAt(aIndex--) - '0' + tag;
            if (sum > 1) {
                sb.insert(0, sum % 2);
                tag = 1;
            } else {
                sb.insert(0, sum);
                tag = 0;
            }
        }

        while (bIndex > -1) {
            sum = b.charAt(bIndex--) - '0' + tag;
            if (sum > 1) {
                sb.insert(0, sum % 2);
                tag = 1;
            } else {
                sb.insert(0, sum);
                tag = 0;
            }
        }

        sb.insert(0, tag == 1 ? tag : "");
        return new String(sb);

    }
}
